The present invention relates generally to cryptographic methods and, more particularly, to authentication protocols using cryptographic methods to authenticate parties involved in a communication.
Encryption is the process of disguising intelligible information, called plaintext, to hide its substance from eavesdroppers. Encrypting plaintext produces unintelligible data called ciphertext. Decryption is the process of converting ciphertext back to its original plaintext. Using encryption and decryption, two parties can send messages over an insecure channel without revealing the substance of the message to eavesdroppers.
A cryptographic algorithm or cipher is a mathematical function used in the encryption and decryption of data. A cryptographic algorithm typically works in combination with a key to encrypt and decrypt messages. The key, typically a large random number, controls the encryption of data by the cryptographic algorithm. The same plaintext encrypts to different ciphertext with different keys. In general, it is extremely difficult to recover the plaintext of a message without access to the key, even by an eavesdropper having full knowledge of the cryptographic algorithm.
In general, there are two types of key-based cryptographic algorithmsxe2x80x94symmetric algorithms and asymmetric algorithms. In symmetric algorithms, also called secret key algorithms, one key is used both for encryption and decryption. Symmetric algorithms require that the sender and receiver of the message agree on a secret key before they can communicate securely. One benefit of symmetric algorithms is that symmetric algorithms execute quickly in a microprocessor. However, key distribution can be a problem, particularly where the communicating parties are in different physical locations. The parties must agree to a key in secret, since anyone possessing the key can encrypt or decrypt messages. If the key is compromised, then an eavesdropper can decrypt any messages encrypted to that key. The eavesdropper could also pretend to be one of the parties and produce false messages to deceive the other party.
The Diffie-Hellman algorithm is a key exchange algorithm that allows two parties to agree on a secret key over an insecure channel without divulging the secret key. According to the Diffie-Hellman algorithm, the parties agree on two, non-secret prime numbers N and G. N is typically a large prime number. The security of the system is based on the difficulty of factoring numbers the same size as N. G may be a one-digit prime number. Each party generates a large random integer, denoted x and y, respectively. The parties then calculate derived numbers X and Y. The first party computes X using the equation X=Gx mod N. The second party computes Y using the equation Y=Gy mod N. The first party transmits X to the second party. The second party transmits Y to the first party. The first party computes the key K using the equation K=Yx mod N. The second party computes the key K using the equation K=XY mod N. K is equal to Gxy mod N. An eavesdropper cannot compute K with knowledge, only of N, G, X, and Y. Therefore, the value K, which was computed independently by the two parties using information exchanged over the insecure channel, may be used by the parties as the secret key for secure communications. The Diffie-Hellman algorithm does not establish the identity of either party, but only allows them to communicate in privacy using the secret key K in a symmetric encryption device.
Asymmetric encryption algorithms, also known as public key algorithms, use different keys for encryption and decryption. The encryption key, also called the public key, can be made public. Anyone can use the public key to encrypt messages. The decryption key, also called the private key, is secret. Only a person with the private key can decrypt messages encrypted with the corresponding public key.
Using an asymmetric encryption algorithm, the sender encrypts a message using the public key of the intended recipient. Only the intended recipient can decipher the message using his private key. Since the private key is not distributed, public key algorithms avoid the problems of key exchange inherent in symmetric algorithms. However, public key algorithms are computationally complex and take longer to execute than symmetric algorithms.
One of the most popular public key algorithms is the RSA algorithm, named after its three inventorsxe2x80x94Ron Rivest, Adi Shamir, and Leonard Adleman. The RSA algorithm is based on a modulus N which is the product of two large prime numbers P and Q. A public exponent E is chosen such that the public exponent E and (Pxe2x88x921)(Qxe2x88x921) are relatively prime, which means they have no prime factors in common. The public exponent E does not have to be a prime number, but it must be smaller than the modulus N and it must be odd. The public exponent E is used to compute a private exponent D such that (DExe2x88x921) is evenly divisible by (Pxe2x88x921)(Qxe2x88x921). This relationship may be written as DE=1 mod(Pxe2x88x921)(Qxe2x88x921). The public key comprises the public exponent E and modulus N. The private exponent D is the private key.
In operation, the sending party divides message bits into blocks smaller than the word length of the modulus N to obtain a word of value X. The message block is encrypted by computing Y=XE mod N, which is a word of length equal to N. The encrypted message is transmitted to the receiving party. The receiving party can decrypt the message by computing X=YD mod N where Y is the ciphertext.
The RSA algorithm and other public key algorithms allow secure communications between two parties, but do not provide means for authenticating the parties. When a person receives a message encrypted with his public key, he can be assured that the content of the encrypted message is secret from all but the sending party, since only he possesses the private key for decrypting the message. However, the party receiving the encrypted message has no assurance of the identity of the sending party, since anyone with his public key could have encrypted the message. If the receiving, party desires to authenticate the sending party""s identity, the sending party may encrypt a message with his secret key. The receiving party can then use the public key to decrypt the message. If the message decrypts successfully, only the sending party could have sent the message. In this case, the ability to authenticate messages has been preserved at the expense of completely giving up secrecy, since anyone with the sender""s public key can decipher the message.
It is known to doubly encrypt messages to provide both secure communications and authentication capability. In this case, each party to the communication possesses a public key used for encrypting messages and a private key used for decrypting messages. Assume that party A wishes to send party B a message. Party A encrypts the message first, using party A""s private key. The resulting ciphertext is encrypted a second time using party B""s public key. The result of the second encryption operation is transmitted to party B. Party B decrypts the message using party B""s private key. Since party B is the only person in possession of the private key, only he can decrypt the message so the communication is secure. The result of the first decryption operation is the inner ciphertext produced by encrypting the original message with party A""s private key. Thus, party B can then use party A""s public key to decrypt the inner ciphertext to obtain the original message. Since only party A possesses the private key that can generate the inner ciphertext, party A""s identity is authenticated to party B.
Key certification authorities have been used in the past to provide a means for obtaining and/or verifying the public key of an intended recipient. The key certification authority issues digital certificates that include a person""s public key and information identifying the person. The digital certificate is signed using the private key of the key certification authority. The signature of the key certification authority attests to the authenticity of the public key and the associated identity.
Digital certificates are used when it is necessary to exchange public keys with someone in a remote physical location. For smaller groups of people who wish to communicate securely, it is relatively easy to manually exchange diskettes or e-mails containing public keys. In cases where manual key distribution is not practical, a person can request a digital key certificate from the key certification authority to obtain the public key of the intended recipient. Thus, the key certification authority has an ongoing role to provide public keys upon request. The public key is distributed in the form of a key certificate signed by the key certification authority. To verify the public key, the sending party simply decrypts the key certificate with the public key of the key certification authority. If the key certificate is successfully decrypted, the public key is validated.
Another method used in the past for authenticating the identity of a party is the challenge response method. The sending party can encrypt a random message, known as the authentication challenge, which is sent to the intended recipient. The intended recipient encrypts the authentication challenge with his or her secret key and sends the reply, known as the authentication response, back to the sending party. The sending party can then decrypt the authentication response using the public key of the second party, which may be obtained from the key certification authority. If the authentication response is successfully decrypted, then the public key obtained from the key certification authority is assumed to be correct and can be used to send messages to the intended recipient.
The present invention is a method for bilateral identity authentication over a communication channel. The present invention allows two parties to authenticate themselves to the other. The present invention further incorporates a key exchange algorithm, such as the Diffie-Hellman algorithm, to enable the parties to compute a session key for use in a symmetric ciphering algorithm.
According to the present invention, each party generates a random bitstring that is used to construct an authentication challenge. Each party encrypts the authentication challenge to the other party""s public key and transmits the encrypted authentication challenge to the other party. The other party is expected to return an authentication response that depends on the other party being able to decipher the authentication challenge.
After receiving the encrypted authentication challenge from the other party, each party deciphers the authentication challenge and generates an authentication response based on the authentication challenge. The authentication response includes bits that the challenging party cannot predict in advance. In one embodiment, each party encrypts the authentication response using the session key computed as a function of the exchanged random bitstrings. Encryption of the authentication response with the session key produces bits that the other party cannot determine in advance since neither party alone is able to determine the session key. Alternatively, the challenged party can blend as yet unknown bits with the bits of the authentication challenge or may return a derivative of the authentication challenge, such as a hash of the authentication challenge.
After receiving an authentication response from the other party, each party verifies that the expected authentication response was received. If not, communications between the parties are terminated. If the identity of both parties is properly authenticated, communications can continue using the session key and a symmetric cipher algorithm.